package util.linkedList.impl;


import util.linkedList.LinkedList;

/**
 * 单向链表
 *
 * @Author Huzz
 * @Created 2021-10-09 14:49
 */
public class SingleLinkedList<T> implements LinkedList {
    /**
     * 表头
     */
    private Node<T> nodeHead;

    /**
     * 节点个数
     */
    private int nodeCount;

    public SingleLinkedList() {
        nodeHead = new Node(null, null);
        nodeCount = 0;
    }

    /**
     * 链表是否为空
     */
    @Override
    public boolean isEmpty() {
        return nodeCount == 0;
    }

    /**
     * 链表长度
     */
    @Override
    public int size() {
        return nodeCount;
    }

    /**
     * 查找节点
     *
     * @param index
     * @return
     */
    private Node<T> getNode(int index) {
        if (nodeCount < 0 || index >= nodeCount) {
            throw new IndexOutOfBoundsException();
        }
        Node<T> node = nodeHead.next;
        for (int i = 0; i < index; i++) {
            node = node.next;
        }
        return node;
    }

    /**
     * 根据所给位置查找节点
     */
    @Override
    public T get(int index) {
        return getNode(index).value;
    }

    /**
     * 查找第一个节点
     *
     * @return
     */
    @Override
    public T getFirst() {
        return getNode(0).value;
    }

    /**
     * 查找最后一个节点
     *
     * @return
     */
    @Override
    public T getLast() {
        return getNode(nodeCount - 1).value;
    }

    /**
     * 在指定位置前插入节点
     *
     * @param index
     * @param data
     */
    @Override
    public void insert(int index, Object data) {
        if (index == 0) {
            Node<T> node = new Node<>(nodeHead.next, (T) data);
            nodeHead.next = node;
            nodeCount++;
            return;
        }

        Node lNode = getNode(index - 1);
        Node<T> node = new Node<>(lNode.next, (T) data);
        lNode.next = node;
        nodeCount++;
        return;
    }

    /**
     * 在链表末尾添加节点
     *
     * @param data
     */
    @Override
    public void append(Object data) {
        insert(nodeCount, (T) data);
    }

    /**
     * 在第一个节点前插入一个节点
     *
     * @param data
     */
    @Override
    public void insertFirst(Object data) {
        insert(0, (T) data);
    }

    /**
     * 删除节点
     *
     * @param index
     */
    @Override
    public void del(int index) {
        Node node = getNode(index);
        if (index == 0) {
            nodeHead.next = node.next;
            node = null;
            nodeCount--;
            return;
        }
        getNode(index - 1).next = node.next;
        node = null;
        nodeCount--;
        return;
    }

    /**
     * 删除第一个节点
     */
    @Override
    public void deleteFirst() {
        del(0);
    }

    /**
     * 删除最后一个节点
     */
    @Override
    public void deleteLast() {
        del(nodeCount - 1);
    }


    /**
     * ======================================定义节点==============================================
     */
    /**
     * 单链表节点定义
     *
     * @param <T>
     */
    private class Node<T> {
        // 后继
        private Node<T> next;
        // 数据
        private T value;

        public Node(Node next, T data) {
            this.next = next;
            this.value = data;
        }
    }
    /** =========================================================================================== */

}
